Embodiments of the invention relate to storage systems, in particular, for parities in multiple dimensions for data recovery.
Considerable interest has arisen lately in coding schemes that combine local and global properties. Applications like Redundant Arrays of Independent Disks (RAID) architectures are an example of this interest. In effect, given an array of storage devices, a regular RAID architecture such as RAID 5, protects against a total storage device failure. The storage devices may be, for example, solid state devices (SSDs), hard disk drives (HDDs), tapes, or other types of storage devices. The RAID 5 architecture is implemented by XORing the contents of the data storage devices, where the outcome of XORing is stored in a parity storage device. Then, if a storage device fails, its contents can be recovered by XORing the contents of the surviving storage devices. However, RAID 5 may be insufficient for large numbers of storage devices. More failures may occur exceeding the erasure-correcting capability of the code. A possible solution is using RAID 6, which adds a second parity, but such an approach may be wasteful.
Other approaches involve using a limited amount of parities, such as one or two extra parities, called global parities. So, if there is an m×n array of storage devices, each row is protected by a parity like in RAID 5. A column of storage devices may represent a box or some other configuration, but it is assumed that a column may fail, in which case each element in the column is recovered row by row (locally), like in RAID 5. But if some extra storage devices have failed in addition to the column, data loss will occur if no extra precautions are taken.